#include <bits/stdc++.h>
using ll=long long;
const int N=1e5+10;
ll n;
using namespace std;
ll myhash[3];
// int main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cin>>n;
//     while(n--)
//     {
//         int x,y,z;
//         //y o u
//         cin>>x>>y>>z;
//         myhash[0]=x;
//         myhash[1]=y;
//         myhash[2]=z;
//         int minl=0;
//         int score=0;
//         for(int i=0;i<3;i++)
//         {
//             minl=min(myhash[0],min(myhash[1],myhash[2]));
//             if(minl>0)
//             {
//                 myhash[0]-=minl;
//                 myhash[1]-=minl;
//                 myhash[2]-=minl;
//                 score+=minl*2;
//             }
//             else if(minl==0)
//             {
//                 if(myhash[1]==1||myhash[1]==0)break;
//                 else if(myhash[1]>=2)
//                 {
//                     // myhash[1]-=1;
//                     score+=myhash[1]-1;
//                     myhash[1]=0;
//                 }
//             }   
//         }
//         cout<<score<<endl;
//     }
//     return 0;
// }

//多源BFS+最短路
//遍历矩阵加入所有的源点到队列里，在BFS()
class Solution {
    public:
        int dx[4]={0,0,1,-1};
        int dy[4]={1,-1,0,0};
        int m,n;
        bool vis[1010][1010]={0};
        int rotApple(vector<vector<int>>& grid) {
           queue<pair<int,int>> q;
           m=grid.size(),n=grid[0].size();
           //先找到所有的烂苹果加入队列
           for(int i=0;i<m;i++)
           {
                for(int j=0;j<n;j++)
                {
                    //加入烂苹果
                    if(grid[i][j]==2)q.push({i,j});
                }
           }
           int ret=0;
           //遍历存储了烂苹果的队列
           while(q.size())
           {
                int sz=q.size();
                ret++;
                while(sz--)
                {
                    auto [a, b]=q.front();
                    q.pop();
                    for(int i=0;i<4;i++)
                    {
                        //向烂苹果的上下左右去扩散，如果没有为1的格子，就遍历下一个烂苹果的格子，直到队列为空
                        int x=a+dx[i],y=b+dy[i];
                        if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&!vis[x][y])
                        {
                            //不修改数组就需要把这里置为访问过的状态，因为需要遍历最后的结果，所以在循环
                            //结束后不能将vis[x][y]置为false
                            vis[x][y]=true;
                            q.push({x,y});    
                        }
                    }
                }
           }

           //输出最后结果
           for(int i=0;i<m;i++)
           {
                for(int j=0;j<n;j++)
                {
                    if(grid[i][j]==1&&!vis[i][j])return -1;        
                }
           }
           return ret-1;
        }
        
    };
// class Solution {
//     public:
//         int LastRemaining_Solution(int n, int m) {
//             //单链表模拟约瑟夫环
//             // list<int> li;
//             // for(int i=0;i<n;i++)li.push_back(i);
//             // auto it=li.begin();
//             // while(li.size()>1)
//             // {
//             //     //从0开始就走多一步了
//             //     for(int i=1;i<m;i++)
//             //     {
//             //         if(++it==li.end())it=li.begin();
//             //     }
//             //     it=li.erase(it);
//             //     if(it==li.end())it=li.begin();
//             // }
//             // return *li.begin();

//             //数组模拟约瑟夫环
//             // vector<int> ret(n);
//             // for(int i=0;i<=n;i++)ret[i]=i;
//             // int index=0;
//             // while(ret.size()>1)
//             // {
//             //     index=(index+m-1)%ret.size();
//             //     ret.erase(ret.begin()+index);
//             // }
//             // return *ret.begin();

//             //递归模拟约瑟夫环
// //             约瑟夫环问题有一个经典的递归公式：

// // 当只有一个人时，该人就是最后剩下的那个人，记为f(1) = 0。
// // 当有n个人时，最后剩下的那个人的位置可以通过以下公式计算：
// // f(n, m) = (f(n-1, m) + m) \% n
// // f(n,m)=(f(n−1,m)+m)%n
// //只能确定最后一个剩的人是谁，删除人的过程不对
//             int last=0;
//             for(int i=2;i<=n;i++)
//             {
//                 last=(last+m)%i;
//                 cout<<last<<" ";
//             }
//             return last;
//         }
        
//     };
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<vector<int>> s({{2,1,1},{1,0,1},{1,1,1}});
    cout<<Solution().rotApple(s);
    // char ch;
    // int m,n;cin>>n>>ch>>m;
    // cout<<Solution().LastRemaining_Solution(n,m);
    return 0;
}
